ТЕМА:  ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

ЗАДАЧА 2.А. Решение задачи линейного программирования графическим методом

 

Внимание!

Это ОЗНАКОМИТЕЛЬНАЯ ВЕРСИЯ работы №2073, цена оригинала 200 рублей. Оформлена в программе Microsoft Word.

Оплата. Контакты.

Вариант 7. Найти максимальное и минимальное значения линейной функции   Ф = 2x₁ — 2·x₂  при ограничениях:              x₁ +   х₂   ≥ 4;

                                                        — х₁ + 2·х₂  ≤ 2;

                                                        x₁ + 2·х₂  ≤ 10;

х _i  ≥ 0,   i = 1,2.

 

Решение:

Заменив условно знаки неравенств на знаки равенств, получим систему уравнений                            x1 +    х2  = 4;

— х1 + 2·х2  = 2;

x1 + 2·х2  = 10.

Построим по этим уравнениям прямые, затем в соответствии со знаками неравенств выделим полуплоскости и получим их общую часть – область допустимых решений ОДР – четырехугольник MNPQ.

Минимальное значение  функ-

ции — в точке М(2; 2)

Ф_min  = 2·2 — 2·2 = 0.

Максимальное значение достигается в точке  N (10; 0),

Ф_max = 2·10  — 2·0 = 20.

 

Вариант 8. Найти максимальное и минимальное значения

линейной функции   Ф = x₁  + x₂

                   при ограничениях:              x₁ — 4·х₂  — 4 ≤ 0;

                                                      3·х₁ —  х₂  ≥ 0;

                                                        x₁ + х₂  — 4 ≥ 0;

х _i  ≥ 0,   i = 1,2.

 

Решение:

Заменив условно знаки неравенств на знаки равенств, получим систему уравнений                                       x1 — 4·х2   = 4 ;

3·х1 —   х2  = 0;

x1 +  х2  = 4 .

Построим по этим уравнениям прямые, затем в соответствии со знаками неравенств выделим полуплоскости и получим их общую часть – область допустимых решений ОДР – неограниченный многоугольник MNPQ.

Минимальное значение  функ-

ции – на прямой NP, например

в точке Р(4; 0 )

Ф_min  = 4 + 0 = 4.

ОДР сверху не ограничена, следовательно,  Ф_max = + ∞.

 

Вариант 10. Найти максимальное и минимальное значения

линейной функции   Ф = 2·x₁ — 3·x₂

                   при ограничениях:                 x₁ + 3·x₂  ≤ 18;

                                                         2·х₁ +   х₂  ≤ 16;

                                                                   х₂  ≤ 5;

3·х₁  ≤ 21;

х _i  ≥ 0,   i = 1,2.

 

Заменив условно знаки неравенств знаками равенств, получим систему уравнений

x₁ + 3·x₂  = 18                    (1);

2·х₁  +   х₂  = 16                    (2);

х₂  = 5                        (3);

3·х₁  = 21                    (4).

Построим по этим уравнениям прямые,  затем в соответствии со знаками неравенств выделим полуплоскости и получим их общую часть  — область допустимых решений ОДР – многоугольник MNPQRS.

Построим вектор Г(2; -3) и через начало координат проведем линию уровня – прямую .

Перемещаем линию уровня в направлении , значение Ф при этом растет. В точке S(7; 0) целевая функция достигает максимума  Ф_max=2·7–3·0= = 14. Перемещаем линию уровня в направлении , значение Ф при этом убывает. Минимальное значение  функции — в точке N(0; 5)

Ф_min  = 2·0 – 3·5 = –15.

 

ЗАДАЧА 2.B. Решение задачи линейного программирования

     аналитическим симплексным методом

Вариант 7. Минимизировать целевую функцию Ф = x₁— x₂+ x₃+ x₄+ x₅ — x₆

Первоначальный базис:  х2, х4, x5

                   при ограничениях:     x₁ + x₄ +6·x₆ = 9,

                                                  3·x₁ + x₂ – 4·x₃ + 2·x₆ = 2,

                                                     x₁ + 2·x₃ + x₅ + 2·x₆ = 6.

 

Решение:

Количество неизвестных  n=6,  количество  уравнений m=3.  Следовательно,  r = n-m = 3 неизвестных можно принять в качестве свободных. Выберем x₁, x₃ и x₆.

Базисные переменные x₂,x₄ и x₅ выразим через свободные и приведем систему к единичному базису

х₂ = 2 — 3·x₁ + 4·x₃ – 2·x₆

x₄ = 9 – x₁ – 6·x₆                   (*)

x₅ = 6 – x₁ — 2·x₃ – 2·x₆

Целевая  функция будет иметь вид:

Ф = x₁ — 2 + 3·x₁ — 4·x₃ + 2·x₆ + x₃ + 9 – x₁ – 6·x₆ +6 – x₁ — 2·x₃ – 2·x₆ – x₆ =

= 13 + 2·x₁ — 5·x₃ – 7·x₆

Положим  x₁ = x₃ =  x₆ = 0,   при этом  базисные переменные примут значения  x₂ = 2;  x₄ = 9;  x₅ = 6,   то есть,  первое  допустимое решение (0;  2;  0;  9;  6;  0),  целевая функция  Ф₁ = 13.

Переменные х₃ и х₆ входят в целевую функцию с отрицательными коэффициентами, следовательно, при увеличении их значений  величина Ф будет уменьшаться.  Возьмем, к примеру, х₆. Из 1-го уравнения системы (*) видно,  что увеличение  значения x₆ возможно до x₆ = 1  (пока x₂ ³ 0).  При этом x₁ и x₃  сохраняют значения, равные нулю. Теперь в качестве базисных переменных примем х₄, х₅, х₆, в качестве свободных – х₁, х₂, х₃. Выразим новые базисные переменные через новые свободные. Получим

х₆ = 1 – 3/2·x₁ – 1/2·x₂ + 2·x₃

x₄ = 3  +   8·x₁ + 3·x₂ – 12·x₃

                                               x₅ = 4 + 2·x₁ +  x₂  – 6·x₃

Ф = 6 + 25/2 ·x₁ + 7/2·x₂ – 19·x₃

Присвоим свободным переменным нулевые значения, то есть, x₁ =x₂= x₃=0,  при этом х₆ = 1, x₄ = 3,  x₅ = 4, то есть, третье допустимое решение (0;  0;  0; 3;  4;  1).   При этом Ф₃ = 6.

Переменная x₃ входит в целевую функцию с отрицательным коэффициентом, следовательно увеличение x₃  относительно нулевого значения приведет к снижению Ф. Из 2-го уравнения видно, что x₃  может возрастать до 1/4, из 3-го уравнения – до 2/3. Второе уравнение более критично. Переменную x₃ переведем в число базисных, x₄ — в число свободных.

Теперь в качестве новых свободных переменных примем x₁, x₂ и x₄. Выразим через них новые базисные переменные x₃, x₅, x₆. Получим систему

х₃ = 1/4 + 2/3·x₁ + 1/4·x₂ – 1/12·x₄

x₅ = 5/2 — 2·x₁ – 1/2·x₂ + 1/2·x₄                                                          

x₆ = 3/2 – 1/6·x₁ –  1/6·x₄

Целевая функция примет вид

Ф = 5/4 — 1/6·x₁  — 5/4·x₂ + 19/12·x₄

Переменные х₁ и х₂  входят в целевую функцию с отрицательными коэффициентами, следовательно, при увеличении их значений  величина Ф будет уменьшаться.  Возьмем, например, х₂. Из 2-го уравнения системы видно,  что увеличение  значения x₂ возможно до x₂ = 5 (пока x₅ ³ 0).  При этом x₁ и x₄  сохраняют  нулевые  значения,  значения других  переменных равны x₃ = 3/2;  x₅ = 0,  x₆ = 3/2, то есть, четвертое допустимое решение (0;  5;  3/2;  0;  0;  3/2).   При этом Ф₄ = 5/4.

Теперь в качестве новых свободных переменных примем x₁, x₄ и x₅. Выразим через них новые базисные переменные x₂, x₃, x₆. Получим систему

х₂ = 5 — 4·x₁ + x₄ – 2·x₅

x₃ = 3/2 – 1/3·x₁ + 1/6·x₄ — 1/2·x₅      

x₆ = 3/2 – 1/6·x₁ –  1/6·x₄

Целевая функция примет вид

Ф = — 5 + 29/6·x₁  + 1/3·x₄ + 5/2·x₅

Коэффициенты при обеих переменных в выражении для Ф положительные,  следовательно, дальнейшее уменьшение величины Ф невозможно.

То есть, минимальное значение Ф_min = — 5,  последнее допустимое  решение (0;  5;  3/2;  0;  0;  3/2)  является оптимальным.

 

 

Вариант 8.  Максимизировать целевую функцию  Ф =  4·x₅ + 2·x₆

Первоначальный базис:  х1, х2, x3, x4

                   при ограничениях:    x₁ +    x₅ +   x₆ = 12;

                                                                x₂ + 5·x₅ —    x₆ = 30;

                                                       x₃ +    x₅ — 2·x₆ = 6;

                                                    2·x₄ + 3·x₅ — 2·x₆ = 18;

Решение:

Количество уравнений равно 4, количество неизвестных – 6. Следовательно r = n – m = 6 – 4 = 2 переменных можем выбрать в качестве свободных, 4 переменных – в качестве базисных. В качестве свободных выберем x₅ и x₆, в качестве базисных — x₁, x₂, x₃, x₄. Выразим базисные переменные через свободные и приведем систему уравнений к единичному базису

x₁ = 12 —   x₅  —   x₆;

x₂ = 30 — 5·x₅  +   x₆;

x₃ =   6 —    x₅  + 2·x₆;

x₄ =  9 —  3/2·x₅ + x₆;

Целевую функцию запишем в виде Ф =  4·x₅ + 2·x₆ . Присвоим свободным переменным нулевые значения x₅  = x₆ =  0. При этом базисные переменные примут значения x₁ = 12,  x₂ = 30,   x₃ =  6,   x₄ =  9, то есть, получим первое допустимое решение (12, 30, 6, 9, 0, ) и Ф₁ = 0.

В целевую функцию обе свободные переменные входят с положительными коэффициентами, то есть, возможно дальнейшее увеличение Ф. Переведем,  например, x₆    в число  базисных.  Из уравнения (1) видно, что x₁ = 0 при x₅ = 12,  в (2) ÷ (4) x₆   входит с положительными коэффициентами. Перейдем к новому базису: базисные переменные – x₆,  x₂,  x₃,  x₄,  свободные — x₁, x_5. Выразим новые базисные переменные через новые свободные

х₆ =  12   —   x₁  —      x₅;

x₂ =  42  —   x₁    —   6·x₅;

x₃ =  30  — 2·x₁  —   3·x₅;

x₄ =  21  —    x₁  — 5/2·x₅;

Целевая функция примет вид    Ф = 24 — 2·x₁ + 2·x₅;

Присвоим свободным переменным нулевые значения x₁  = x₅ =  0. При этом базисные переменные  примут значения x₆ =12,  x₂ =42,   x₃ =  30,   x₄ =  21, то есть, получим второе допустимое решение (0, 42, 30, 21, 0, 12 ) и Ф₂ = 24.

В целевую функцию x₅   входит с положительным коэффициентом, то есть, возможно дальнейшее увеличение Ф. Перейдем к новому базису: базисные переменные – x₆,  x₅,  x₃,  x₄,  свободные — x₁, x_2. Выразим новые базисные переменные через новые свободные

х₆ =  5    —    5/6·x₁  +  1/6·x₂;

x₅ =  7    —    1/6·x₁    —   1/6·x₂;

x₃ =  9    —    3/2·x₁  +   1/2·x₂;

x₄ =  7/2 —  7/12·x₁  + 5/12·x₅;

Целевая функция примет вид    Ф = 38 – 7/2·x₁ – 1/3·x₂;

Присвоим свободным переменным нулевые значения x₁  = x₂ =  0. При этом базисные переменные  примут значения x₆ = 5,  x₅ = 7,   x₃ =  9,   x₄ =  7/2, то есть, получим третье допустимое решение Х₃ = (0,  0, 9, 7/2, 7, 5 ) и Ф₃ = 38.

В целевую функцию обе переменные   входят с отрицательными коэффициентами, то есть, дальнейшее увеличение Ф невозможно.

Следовательно, последнее допустимое решение является оптимальным, то есть,  Х_опт = (0, 0, 9, 7/2, 7, 5)  и  Ф_max = 38.

 

 

Вариант 10.  Максимизировать целевую функцию  Ф = x₂ + x₃  

Первоначальный базис:  х1, х4

                    при ограничениях:       x₁ —    x₂ + x₃ = 1,

                                                          x₂ — 2·х₃ + х₄ = 2.                

 

Решение:

Система уравнений — ограничений  совместна, так как  ранги матрицы системы  уравнений и  расширенной матрицы одинаковы и  равны 2. Следовательно, две переменные можно  принять в качестве свободных, две другие переменные — базисные — выразить линейно через две свободные.

Примем за свободные переменные x₂ и х₃.Тогда базисными будут переменные  х₁ и х₂, которые выразим через свободные

x₁ = 1 + x₂  —  x₃;                             (*)

x₄ = 2 — x₂ + 2·x₃;

Целевая функция уже выражена через x₂ и x₃,  то есть,  Ф = x₂ + x₃.

При х₂=0 и х₃=0 базисные переменные будут равными х₁ = 1,  х₄ = 2.

Имеем первое допустимое решение Х₁ = (1, 0, 0, 2),  при этом  Ф₁ = 0.

Увеличение Ф возможно при увеличении, например, значения х₃, который входит в выражение для Ф с положительным коэффициентом (x₂ при этом остается равным нулю). В первое уравнение системы (*) видно, что х₃ можно увеличивать до 1 (из условия х₁ ³0), то есть это уравнение накладывает ограничение на увеличение значения х₃. Первое уравнение системы (*) является разрешающим. На базе этого уравнения переходим к новому базису, поменяв  х₁ и х₃ местами. Теперь базисными переменными будут  х₃ и  x₄, свободными —  x₁ и  x₂. Выразим теперь х₃ и x₄ через х₁ и х₂.

Получим:               x₃ = 1 — x₁ + x₂;                    (**)

x₄ = 4 — 2·x₁ + x₂;

Ф = х₂ + 1 — х₁ + х₂ = 1 — x₁ + 2·x₂

Приравняв нулю свободные переменные, получим второе допустимое базисное решение Х₂= (0; 0; 1; 4), при котором Ф₂=1.

 

Увеличение Ф возможно при увеличении х₂. Увеличение же х₂, судя по последней  системе  уравнений (**), не ограничено. Следовательно, Ф будет принимать все большие положительные  значения, то есть, Ф_мах = + ¥.

Итак,  целевая функция Ф не ограничена сверху, потому оптимального решения не существует.

 

 

ЗАДАЧА 2.D. Составить задачу, двойственную к приведенной

исходной задаче.

Вариант 7. Максимизировать целевую функцию Ф = 2×х₁ — х₄

                   при ограничениях:                         х₁ + х₂  =  20,

                                                                             х₂ + 2×х₄ ≥  5,

      х₁ + х₂ + х₃ ≤ 8,

                                                                   х_i ≥ 0    (i = 1, 2, 3, 4)

Решение:

Приведем систему ограничений к единому, например, каноническому виду, введя дополнительные переменные во 2-ое и 3-е уравнения

х₁ + х₂  =  20,

х₂ + 2×х₄ – х₅  =  5,

— х₁ + х₂ + х₃ + х₆ = 8.

Получили несимметричную задачу 2-го типа. Двойственная задача будет иметь вид:

Минимизировать целевую функцию F = 20×у₁ + 5×y₂ + 8×y₃

при             y₁  —        y₃ ≥ 2,

y₁ + y₂ + y₃ ≥ 0,

y₃ ≥ 0,

2×y₂      ≥ 1,

-y₂      ≥ 0,

y₃ ≥ 0.

Вариант 8. Максимизировать целевую функцию  Ф = х₂ — х₄ — 3×х₅

                   при ограничениях:            х₁ + 2×х₂ —    х₄  + х₅ = 1,

                                                         — 4×х₂ +    х₃ + 2×х₄ — х₅ = 2,

                                                                  3×х₂ +    х₅ +    х₆ = 5,

                                                                  x_i ≥ 0,                   (i = 1,  6)

 

Решение:

Имеем исходную задачу на максимизацию с системой ограничений в виде уравнений, то есть, пара двойственных задач имеет несимметричный вид 2-го типа, математическая модель которых в матричной форме имеет вид:

Исходная задача:                                              Двойственная задача:

Ф = С×Х          max                                   F = B^Т×Y       min

при   А×Х = В                                           при A^Т×Y ≥ С^Т

Х ≥ 0

В исходной задаче матрица-строка коэффициентов при переменных в целевой функции  имеет вид   С = (0;  1;  0;   -1;   -3;   0),

матрица-столбец свободных членов и матрица коэффициентов при переменных в системе ограничений имеют вид

1                            1     2     0    -1     1     0

В =     2      ,          А =     0   — 4     1     2    -1     0

5                            0     3     0     0     1     1

Найдем транспонированную матрицу коэффициентов, матрицу-строку коэффициентов при переменных в целевой функции и матрицу-столбец свободных членов

1     0     0                                     0

2     4     3                                     1

0     1     0                                     0                 В^Т = (1;   2;   5)

A^T =           -1     2     0              С^Т =      -1

1    -1     1                           -3

0     0     1                                     0

Двойственная задача запишется в следующем виде:

найти минимальное значение целевой функции F = y₁ + 2×y₂ + 5×y₃

при ограничениях         y₁                      ≥  0,

2×y₁ — 4×y₂ + 3×y₃ ≥  1,

y₂        ≥  0,

— y₁ + 2×y₂        ≥  -1,

y₁ —   y₂ +   y₃ ≥  -3,

y₃ ≥  0,

 

Вариант 10. Минимизировать функцию    Ф = х₁ + х₂ + х₃

при ограничениях:             3×х₁ + 9×х₂ + 7×х₃  ≥ 2,

                                                        6×х₁ + 4·х₂ + 5×х₃  ≥ 3,

                                                        8×х₁ + 2·х₂ + 4×х₃  ≥ 4,

Решение:

Имеем исходную задачу на минимизацию с системой ограничений в виде неравенств, то есть, пара двойственных задач имеет симметричный вид 3-го типа, математическая модель которых в матричной форме имеет вид:

Исходная задача                                               Двойственная задача

Ф = С× Х         min                                    F = B^Т×Y       max

при   А × Х  ≥ В                                        при A^Т ×Y  ≤ С^Т

Х ≥ 0                                                Y ≥ 0

В исходной задаче матрица-строка коэффициентов при переменных в целевой функции, матрица-столбец свободных членов и матрица коэффициентов при переменных в системе ограничений имеют вид

2                              3    9    7

С = (1; 1; 1),        В =      3     ,                  А  =       6    4    5

4                              8    2    4

Найдем матрицы двойственной задачи

2                           3    6    8

В^T = (2; 3; 4)                С^T =  3            A^T =     9    4    2

4                         7    5    4

Двойственная задача формулируется в виде:

Максимизировать целевую функцию     F = 2y₁ + 3y₂ + 4y₃

при ограничениях        3×y₁  + 6×y₂ + 8×y₃ ≤ 1,

9×y₁ +  4×y₂ + 2×y₃ ≤ 1,

7×y₁ +  5×y₂ + 4×y₃ ≤ 1,

y_i ≥ 0   (i = 1, 2, 3)

 

ЗАДАЧА 2.С. Решение задачи линейного программирования с помощью симплексных таблиц.

 

 

Вариант 7. Максимизировать целевую функцию Ф = 2·x₁ — x₂ + 3·x₃+ 2·x₄

Первоначальный базис:  х1, z1, z3

         при ограничениях: 2·x₁  +  3·x₂   —   x₃ + 2·x₄ ≤ 4,

                                                                x₁  —   2·x₂ + 5·x₃ — 3·x₄ ≥ 1,

     4·x₁  + 10·x₂   +3·x₃ +   x₄ ≤ 8.

 

Решение:

Приведем систему ограничений к каноническому виду

2·x₁  +  3·x₂   —   x₃ + 2·x₄ + z₁  = 4,                           (1)

x₁  —   2·x₂ + 5·x₃ — 3·x₄ —  z₂  = 1,                            (2)

4·x₁  + 10·x₂   +3·x₃ +   x₄ + z₃  = 8.                          (3)

Имеем систему 3-х уравнений с 7-ю неизвестными. Выберем в качестве базисных 3 переменных x₁, z₁, z₃, в качестве свободных — x₂, x₃ , x₄, z₂ , выразим через них базисные переменные.

Из (2) имеем       x₁ = 1 + 2·x₂ — 5·x₃ + 3·x₄ + x₆

 

Подставим в (1) и (3), получим

x₁  —    2·x₂ +  5·x₃  —  3·x₄  —     z₂  = 1,

z₁  +   7·x₂ — 11·x₃  +  8·x₄ +  2·z₂  = 2,

z₃  +  18·x₂ — 17·x₃ + 13·x₄ + 4·z₂  = 4,

Ф — 3·x₂ + 7·x₃ — 8·x₄ — 2· z₂  = 2.

Составим симплекс-таблицу       

 

 

I итерация                                                                             Таблица 1

Базисн. перем.	Свобод. перем.	x1	x2	x3	x4	z1	z2	z3	bi/aip	aip/aqp
x1	1	1	— 2	5	— 3	0	— 1	0		3/8
z1	2	0	7	-11		1	2	0	1/ 4	1/8
z3	4	0	18	-17	13	0	4	1	4/13	13/8
Ф	2	0	— 3	7	— 8	0	— 2	0		1

Х₁ = (1;  0;  0;  0;  2;  0;   4)             Ф₁ = 2.

 

 

II итерация                                                                                     Таблица 2

x1	14/8	1	5/8	7/8	0	3/8	-2/8	0	2	— 1
x4	1/ 4	0	7/8	-11/8	1	1/8	2/8	0		11/7
z3	6/8	0	53/8		0	-13/8	6/8	1	6/7	8/7
Ф	4	0	4	— 4	0	1	0	0		32/7

Х₂ = (14/8;  0;  0;  1/4;  0;    0;    4)           Ф₂ = 4.

 

 

III итерация                                                                          Таблица 3

x1	1	1	— 6	0	0		-1	— 1		1/2
x4	10/ 7	0	79/7	0	1	-17/7	10/7	11/7		11/7
x3	6/7	0	53/7	1	0	-13/7	6/7	8/7		13/14
Ф	52/7	0	240/7	0	0	-45/7	24/7	32/7		45/14

Х₃ = (1;  0;  6/7;  10/7;  0;    0;    0)           Ф₃ = 52/7.

 

IV итерация                                                                          Таблица 4

z1	1/ 2	1/2	— 3	0	0	1	-1/2	-1/2
x4	37/ 14	17/14	56/14	0	1	0	3/14	5/14
x3	25/14	13/14	28/14	1	0	0	-1/14	3/14
Ф	149/14	45/14	15	0	0	0	3/14	19/14

Х₄ = (0;  0;  25/14;  37/14;  1/2;    0;    0)            Ф₄ = 149/14.

 

В индексной строке последней таблицы нет отрицательных чисел, то есть, в выражении для целевой  функции все Г_i < 0. Имеем случай I, следовательно, последнее базисное решение является оптимальным.

Ответ:  Ф_max= 149/14,

оптимальное решение (0; 0; 25/14;  37/14;  1/2;  0;   0)

 

 

Вариант 8.  Минимизировать целевую функцию Ф = 5·x₁ — x₃

Первоначальный базис:  х1, х2

                    при ограничениях:  x₁ +    x₂ + 2·x₃ — x₄ =  3,

                                                      x₂ + 2· x₄  =1,

 

Решение:

Количество переменных равно 4, ранг матрицы — 2, следовательно количество свободных переменных равно r = 4 — 2 = 2,  количество базисных тоже 2.  В качестве свободных переменных примем  х₃, х₄, базисные переменные x₁, x₂  выразим через свободные и приведем систему к единичному базису:

x₂ = 1 — 2· x₄,

x₁ =  3 — x₂ — 2·x₃ + x₄ = 3 – 1 + 2· x₄— 2·x₃ + x₄ = 2 — 2·x₃  + 3· x₄

Ф = 5·x₁ — x₃ = 5·(2 — 2·x₃  + 3· x₄) — x₃ = 10 — 10·x₃ + 15· x₄ — x₃ = 10 — 11·x₃ + 15· x₄

Запишем систему уравнений и целевую функцию в удобном для симплекс-таблицы виде, то есть,    x₂ + 2· x₄= 1,

x₁+2·x₃  — 3· x₄ = 2

Ф + 11·x₃ — 15· x₄= 10

Составим таблицу

I итерация                                                                   Таблица 1

Базисн. перем.	Свобод. перем.	Х1	Х2	Х3	Х4	bi/aip	aip/aqp
X1	2	1	0		— 3		1/2
X2	1	0	1	0	2
Ф	10	0	0	11	— 15		— 11/2

Х₁ = (2;  1;  0;  0)          Ф₁ = 10.

 

 

II итерация                                                                           Таблица 2

X3	1	1/2	0	1	-3/2		3/4
X2	1	0	1	0			1/2
Ф	— 1	— 11/2	0	0	3/2		— 3/4

Х₂ = (0;  1;  1;  0)          Ф₂ = -1.

 

III итерация                                                                 Таблица 3

X3	7/4	1/2	3/4	1	0
X4	1/2	0	1/2	0	1
Ф	— 7/4	— 11/2	— 3/4	0	0

Х₃ = (0;  0;  7/4;  1/2)             Ф₃ = -7/4.

 

В индексной строке последней таблицы нет положительных чисел, то есть, в выражении для целевой  функции все Г_i > 0. Имеем случай I, следовательно, последнее базисное решение является оптимальным.

Ответ:  Ф_min = -7/4,        оптимальное решение (0;  0;  7/4;  1/2)

 

********************

Вариант 10. Минимизировать целевую функцию Ф = x₁ + x₂,

Первоначальный базис:  х1, х2, x5

                   при ограничениях:     x₁ –2·x₃ + x₄ = 2,

                                                           x₂ – x₃ + 2·x₄ = 1,

 

Решение:

Количество переменных равно 5, ранг матрицы — 3, следовательно количество свободных переменных равно  r = 6-3 = 2. В качестве свободных переменных примем х₃ и х₄, в качестве базисных — x₁, x₂, x₅. Все уравнения системы уже приведены к единичному базису (базисные переменные выражены через свободные), но записаны в виде, не удобном к применению симплекс-таблиц. Запишем систему уравнений в виде

x₁ —  2·x₃ +  x₄ = 2

x₂ —     x₃ +2·x₄ = 1

x₅ +    x₃  —  x₄. = 5

Целевую функцию выразим через свободные переменные и запишем в виде                                            Ф — 3·x₃ +3·x₄ =  3

Составим таблицу

I итерация                                                                             Таблица 1

Базисн. перем.	Свобод. перем.	х1	х2	х3	х4	х5	bi/aip	aip/aqp
х1	2	1	0	-2	1	0	2	-1/2
х2	1	0	1	-1		0	1/2	1/2
х5	5	0	0	1	-1	1		1/2
Ф	3	0	0	-3	3	0		-3/2

Х₁ = (2;  3;  0;  0;  5)     Ф₁ = 3.

Таблица 2

х1	3/2	1	-1/2	-3/2	0	0
х4	1/2	0	1/2	-1/2	1	0
х5	11/2	0	1/2	1/2	0	1
Ф	3/2	0	-3/2	-3/2	0	0

Х₂ = (3/2;  0;  0;  1/2;  11/2)   Ф₂ = 3/2.

 

В индексной строке последней таблицы нет положительных чисел, то есть, в выражении для целевой функции все Гi > 0. Имеем случай 1, следовательно, последнее базисное решение является оптимальным.

Ответ :  Ф_min= 3/2, оптимальное решение (3/2;  0;  0;  1/2;  11/2).